Edge detection through convolutional operation

In this presentation, I’ll show how to get the edge image on the right with convolutional operation.

First of all, what is convolutional operation?

Let’s say we have a 6x6 matrix and a 3x3 filter. To perform convolutional operation, we would loop over the 6x6 matrix with our filter. For example, we’ll first locate a 3x3 matrix on the 6x6 matrix, and we are going to get the sum of the element-wise products of the filter and the 3x3 matrix we located. We repeat this process until we looped through the entire matrix.

Convolutional operation example

Convolitional Operation in action

Let’s see some simple edge detection examples in Python.

Switch to Jupyter notebook

Now, we know what convolutional operation is, let’s get started on detecting the edges.

Steps needed for edge detection

  1. Load image as an array with readJPEG or readPNG
  2. Convert image to black and white
  3. Pick a filter
  4. Apply convolutional operation with a nested for loop.

Step 1: Load image

img <- readJPEG("minions2.jpeg")
class(img)
## [1] "array"
# dim() returns the height, width, number of color channel, respectively 
dim(img)
## [1] 621 316   3
original_image <- readImage("minions2.jpeg")
display(original_image, method = "raster")

Step 2: Convert image to black and white

There are three methods for converting color to grayscale.

  1. lightness: \(\frac{\text{max}(R, G, B) + \text{min}(R, G, B)}{2}\)

  2. average: \(\frac{R + G + B}{3}\)

  3. luminosity: \(0.2126 R + 0.7152 G + 0.0722B\)

I would use luminosity method for this example.

# Get the dimension of the image and store it in dimension
dimension <- dim(img)

n <- dimension[1]
m <- dimension[2]
d <- dimension[3]
# bw_img is a copy of the original image
bw_img <- img

# loop over every pixel of the imge with a nested for loop
for (row in 1:n){
  for (col in 1:m){
    bw_img[row,col,1:3] <- 0.2126*img[row,col,1]+
      0.7152*img[row,col,2]+0.0722*img[row,col,3]
  }
}

writeJPEG(bw_img, target ="bw_new.jpeg")

black_white <- readImage("bw_new.jpeg")
display(black_white, method = "raster")

Step 3: Pick a filter

Some commonly used filters are listed below. The values in the filter can also be learned by machine for some complicated images.

Note: There are vertical filter and horizontal filter. Horizontal filter is the transpose of the vertical filter.

  • Prewitt filter

\[\begin{vmatrix} 1 & 0 & -1\\ 1 & 0 & -1\\ 1 & 0 & -1 \end{vmatrix}\]

  • Sobel filter

\[\begin{vmatrix} 1 & 0 & -1\\ 2 & 0 & -2\\ 1 & 0 & -1 \end{vmatrix}\]

  • Scharr filter

\[\begin{vmatrix} 3 & 0 & -3\\ 10 & 0 & -10\\ 3 & 0 & -3 \end{vmatrix}\]

# Sodel filter 
vertical_filter <- matrix(c(1,2,1, 0,0,0,-1,-2,-1),3,3)
horizontal_filter <- t(vertical_filter)
vertical_filter
##      [,1] [,2] [,3]
## [1,]    1    0   -1
## [2,]    2    0   -2
## [3,]    1    0   -1
horizontal_filter
##      [,1] [,2] [,3]
## [1,]    1    2    1
## [2,]    0    0    0
## [3,]   -1   -2   -1

Step 4: Apply convolutional operation with a nested for loop.

Main idea:

  • We loop over the whole image and locate a 3x3 matrix at each step
  • In each step, we calculate the vertical and horizontal scores. The edge score equals to \(\sqrt{\text{ver_score}^2+\text{hor_score}^2}\). Sometimes, formula \(|\text{ver_score}|+|\text{hor_score}|\) is used as well.

Let’s demonstrate this computation.

  1. Locate a 3x3 matrix on the image
local <- bw_img[1:3, 1:3,1]
local
##      [,1] [,2] [,3]
## [1,]    1    1    1
## [2,]    1    1    1
## [3,]    1    1    1
  1. compute the horizontal score
# apply convolution operator 
# that is get element-wise product  
horizontal_filter*local
##      [,1] [,2] [,3]
## [1,]    1    2    1
## [2,]    0    0    0
## [3,]   -1   -2   -1

Since the matrix we located have 1s everywhere, horizontal_filter*local gives back the horizontal filter.

# horizontal score is the sum of element-wise products
horiz_score <- sum(horizontal_filter*local)
horiz_score
## [1] 0
  1. compute the vertical score
verti_score <- sum(vertical_filter*local)
verti_score
## [1] 0
  1. Compute edge score.

Edge score is assignment back to the corresponding location, [1,1] in this case, as color value.

sqrt(verti_score^2+horiz_score^2)
## [1] 0

Complete computation is shown below.

# create a copy of the original image to store edge scores 
edge_img <- img

#Loop over the image and compute edge scores
for (row in 1:(n-2)){
  for (col in 1:(m-2)){
    local <- bw_img[row:(row+2), col:(col+2),1]
    horiz_score <- sum(horizontal_filter*local)
    verti_score <- sum(vertical_filter*local)
    edge_img[row,col,1:3]<-sqrt(verti_score^2+horiz_score^2)
  }
}
# Colors are represented as values between 0 and 1 in R. 
# Divide all the values by max to ensure that all the values are between 0 and 1
edge_img <- edge_img/max(edge_img)
writeJPEG(edge_img, target ="edge_img.jpeg")

Let’s check our final image.

edge_img <- readImage("edge_img.jpeg")
display(edge_img, method = "raster")

I defined a function edge_detect that combine all the steps above. It takes three inputs, image path, image format, and filter. Let’s use this function and compare the three filters, Prewitt, Sobel, and Scharr. Below are the edge image resulting from the filters.

I don’t see much difference here with these three classic filters. What about other filters?

You may have noticed that the three filters we used all had 0s as the middle column and the first and third columns are only different by a negative sign. I tested different filters and confirmed that as long as our filter possess this feature, it can detect edge quite well.

Here are some examples:

filter1 <- matrix(c(4,5,6,7, 0,0,0,0,0,0,0,0,-4,-5,-6,-7),4,4)
filter1
##      [,1] [,2] [,3] [,4]
## [1,]    4    0    0   -4
## [2,]    5    0    0   -5
## [3,]    6    0    0   -6
## [4,]    7    0    0   -7
display_mt(edge_detect("minions2.jpeg", type = "jpeg", filter = filter1))

filter1 <- matrix(c(4,5,6,0,0,0,-5,-6,-7),3,3)
filter1
##      [,1] [,2] [,3]
## [1,]    4    0   -5
## [2,]    5    0   -6
## [3,]    6    0   -7
display_mt(edge_detect("minions2.jpeg", type = "jpeg", filter = filter1))

filter1 <- matrix(c(1,2,3,0,0,0,4,5,6),3,3)
filter1
##      [,1] [,2] [,3]
## [1,]    1    0    4
## [2,]    2    0    5
## [3,]    3    0    6
display_mt(edge_detect("minions2.jpeg", type = "jpeg", filter = filter1))

Note: The method above did not do any padding (padding means adding 0s around the image). Due to the natural of mapping, we lost information on the edge of the image. Since most image has important information at the center, the lost is not significant for most cases.

Make improvements

For a better result, I need to complete the following steps (Canny Edge Detection).

  1. Noise Reduction: Apply Gaussian filter to smooth the image.

  2. Apply filter (What I did above).

  3. Non-maximum suppression: The goal is to make thin edges. In this step, we go over every pixel in the image. If the pixel is the maximum along the edge direction, we keep the color value, otherwise, we set the value to 0.

  4. Classify strong, weak, non-relevant pixels: In this step, we classify each pixel as strong, weak, or non-relevant. We change the color value of the pixel based its class.

  5. Edge Tracking by Hysteresis: In this step, we will transform weak pixels into strong ones, if and only if the weak pixel is surrounded by at least one strong pixel.

reference

Improved edge image on the right.

1. Noise Reduction

Gaussian filter is defined as

\[g(x,y)=\frac{1}{2\pi\sigma^2}e^{-\frac{(x)^2+(y)^2}{2\sigma^2}}\]

Gaussian_blur_1(5,1.4)
##            [,1]       [,2]       [,3]       [,4]       [,5]
## [1,] 0.01054991 0.02267864 0.02926890 0.02267864 0.01054991
## [2,] 0.02267864 0.04875119 0.06291796 0.04875119 0.02267864
## [3,] 0.02926890 0.06291796 0.08120150 0.06291796 0.02926890
## [4,] 0.02267864 0.04875119 0.06291796 0.04875119 0.02267864
## [5,] 0.01054991 0.02267864 0.02926890 0.02267864 0.01054991

Comparing original image, black and white image, and smoothed image

2. Apply filter

Note: In convolu_ope I also calculated the angle of the edge, which will be used in the next step, Non-maximum Suppression.

Let’s see check the image after applying Sobel filter.

3. Non-maximum suppression to make thin edges

The goal of non-maximum suppression is to thin out the edges.

There are only two outcomes for each pixel.

  1. We keep the value of the pixel when it is the maximum in the edge direction
  2. We set the value to 0 when it is not the maximum.

Each pixel in the image has a color value and angle value (we calculated the angle value along with the convolutional operation, it equals to \(arctan(\frac{\text{hori_score}}{\text{-verti_score}})\))

Each pixel is surrounded by other 8 pixels. The pixel at the center is compared with the other two pixels. Which two? It depends on the angle of the pixel. See below.

Below are images before and after non-max suppression(on the right).

4. Classify strong, weak, non-relevant pixels

In this step, we first identify each pixels as strong, weak, or non-relevant. Next, we reset color values based on the classes.

  • strong means higher than high threshold
  • weak means between high and low threshold
  • non-relevant means lower than low threshold

Below are images before and after resetting color values based on the classes(on the right).

5. Edge Tracking by Hysteresis

In this step, we will transform weak pixels into strong ones, if and only if the weak pixel is surrounded by a strong pixel.

Comparison of images from Step 3, Step 4, Step 5.

Finally, I defined a function edge_detection that does all the five steps together. Below are the original image and edge images filter by three different filters, Prewitt, Sobel, and Scharr (from left to right, respectively)

There’s no/little difference between these edge images again.

Let’s try some other filters.

img <- readPNG("monarch_in_may.png")
filter1 <- matrix(c(1,1,1, 1,1,0,1,0,0),3,3)
filter1
##      [,1] [,2] [,3]
## [1,]    1    1    1
## [2,]    1    1    0
## [3,]    1    0    0
display_mt(edge_detection(img, filter =filter1))

filter2 <- matrix(c(1,2,3, 0,0,0,-4,-5,-6),3,3)
filter2
##      [,1] [,2] [,3]
## [1,]    1    0   -4
## [2,]    2    0   -5
## [3,]    3    0   -6
display_mt(edge_detection(img, filter =filter2))

filter3 <- matrix(c(10,20,30 ,0,0,0,-10,-20,-30),3,3)
filter3
##      [,1] [,2] [,3]
## [1,]   10    0  -10
## [2,]   20    0  -20
## [3,]   30    0  -30
display_mt(edge_detection(img, filter =filter3))